\bigskip
\bigskip
{\magonebf 6.1.6 Algorithms }

%\bigskip
%$\bullet$ {\bf Line sweep for straight line segments}
%\medskip
%\cleartabs
%\+$void$\quad SWEEP\_SEGMENTS(&$list(segment)\&\ L_1$,\cr
%\+                            &$list(segment)\&\ L_2$,\cr
%\+                            &$GRAPH(point,int)\&\ G$ ) \cr
%
%SWEEP\_SEGMENTS takes as input two lists $L_1$ and $L_2$ of straight
%line segments and performs a plane sweep to construct the arrangement $G$ 
%defined by these segments. Each node $v$  of $G$ corresponds to a point of 
%intersection $G$.inf($v$) between two segments in $S = L_1 \cup L_2$. Every 
%edge  $e=(v,w)$ represents the part the segment $s \in S$ connecting 
%intersection points $G$.inf($v$) and $G$.inf($w$). With $e$ is associated an 
%integer information $G$.inf($e$) which is equal to 0 if $s \in L_1$ and equal 
%to 1 if $s \in L_2$. The direction of $e$ corresponds to the direction of $s$.
%
%Running Time: $O((n+k)\log n)$ , where $n$ is the total number of segments,
%and $k$ is the number of intersections.
%

\bigskip
$\bullet$ {\bf Line segment intersection}

$void$\quad SEGMENT\_INTERSECTION($list(segment)\&\ L,\ list(point)\&\ P$);

SEGMENT\_INTERSECTION takes a list of segments $L$ as input and computes 
the list of intersection points between all segments in $L$.

Running Time: $O((n+k)\log n)$ , where $n$ is the number of segments,
and $k$ is the number of intersections.



\bigskip
$\bullet$ {\bf Convex hull of point set}

$polygon$\quad CONVEX\_HULL($list(point)\ L$);

CONVEX\_HULL takes as argument a list of points and returns the polygon
representing the convex hull of $L$. It is based on a randomized incremental 
algorithm. 

Running Time: $O(n\log n)$ (with high probability), where $n$ is the number 
of segments.


\bigskip
$\bullet$ {\bf Voronoi Diagrams}
\medskip
$void$\quad VORONOI$(list(point)\&\ sites,\ real\ R,\ GRAPH(point,point)\&\ G)$

VORONOI takes as input a list of points  $sites$ and a real number 
$R$. It computes a directed graph $G$ representing the planar subdivision
defined by the Voronoi-diagram of $sites$ where all ``infinite" edges have
length $R$. For each node $v$ $G$.inf($v$) is the corresponding Voronoi 
vertex ($point$) and for each edge $e$  $G$.inf($e$) is the site ($point$) 
whose Voronoi region is bounded by $e$. 

